package independent;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-14
 * Time: 15:13
 */

//插入排序
public class InsertSort {
    //基本思想:把n个待排序的元素 看成一个有序表和一个无序表
    //开始的时候有序表只有一个元素 无序表有(n-1)元素
    //每次从无序表中取出第一个元素 然后在有序表中找到适当的为止插入其中
    //最后成为一个新的有序表
    public static void main1(String[] args) {
        int[] arr = {43,25,7,58,16,4};
        //先定义无序表 i=1 无序表的第一个元素
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            //在定义有序表中的元素的下标
            int j = i-1;
            for (; j >= 0 ; j--) {
                //arr[j] 就是目前有序数组中最大了的 最大的都没tmp大的话 直接退出循环
                if (tmp < arr[j]){
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            //如果是直接退出循环之后 在将tmp的值放回来
            arr[j+1] = tmp;
        }
        System.out.println(Arrays.toString(arr));
    }


    //第二节解法
    public static void main(String[] args) {
        int[] arr = {43,25,7,58,16,4};

        //从无序表的第一个开始
        for (int i = 1; i < arr.length; i++) {
            //也是先定义一个待插入的数 无序数组的首元素
            int insertVal = arr[i];
            //这是有序数组的最后一个元素的下标
            int insertIndex = i-1;

            //insertIndex >= 0 保证了回退不越界
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1] = insertVal;
        }
        System.out.println(Arrays.toString(arr));
    }
}